package com.coder.algorithm.leetcode

import com.coder.algorithm.struct.ListNode

/**
 * [328. 奇偶链表](https://leetcode-cn.com/problems/odd-even-linked-list/)
 *
 * @author yuhus
 * @date: 2022/4/2
 */
object l_0328 {
    /**
     * 原地改变顺序，将 head 作为奇数链表
     */
    fun oddEvenList(head: ListNode?): ListNode? {
        var odd = head
        var evenHead = head?.next
        var even = evenHead
        // even.next = null, 代表没有奇数节点了
        while (even?.next != null){
            odd?.next = even.next
            odd = odd?.next
            even.next = odd?.next
            even = even.next
        }
        odd?.next = evenHead
        return head
    }

    /**
     * 将删除的节点挂载载奇偶链表后面
     */
    fun oddEvenList_1(head: ListNode?): ListNode? {
        var oddHead: ListNode? = null
        var oddTail: ListNode? = null
        var evenHead: ListNode? = null
        var evenTail: ListNode? = null
        var cur = head
        var del: ListNode? = null
        // 第一额节点为 奇数
        var isOdd = true
        while (cur != null) {
            del = cur
            cur = cur.next
            del.next = null
            if (isOdd) {
                if (oddTail == null) {
                    oddHead = del
                    oddTail = del
                } else {
                    oddTail.next = del
                    oddTail = del
                }
            } else {
                if (evenTail == null) {
                    evenHead = del
                    evenTail = del
                } else {
                    evenTail.next = del
                    evenTail = del
                }
            }
            isOdd = !isOdd
        }
        oddTail?.next = evenHead
        return oddHead
    }
}